package org.labuladong.暴力搜索算法.回溯算法;

import java.util.LinkedList;
import java.util.List;

/**
 * @Auther: qingle
 * @Date: 2024/10/25-15:59
 * @Description:
 * 给定⼀个仅包含数字 2-9 的字符串，返回所有它能表示的字⺟组合。
 * 答案可以按任意顺序 返回。
 * 给出数字到字⺟的映射如下（与电话按键相同）。注意 1 不对应任何字⺟。
 * 2：abc 3：def 4：ghi 5：jkl 6：mno 7：pqrs 8：tuv 9：wxyz
 *
 * 输⼊：digits = "23"
 * 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
 *
 * //TODO 组合问题本质上就是遍历⼀棵回溯树，套⽤回溯算法代码框架即可。
 * @version: 1.0
 */
public class LC_17_电话号码的字母组合2 {

	  // 映射表, 将数字映射为对应的字母,mapping的索引从0开始，1开始，0没有用，1没有用，2 abc，3 def，4 ghi，5 jkl，6 mno，7 pqrs，8 tuv，9 wxyz
		String[] mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

		List<String> res = new LinkedList<>();

		// 回溯算法,步骤：
	// 1. 递归终止条件：sb的长度等于digits的长度，说明已经找到了一个完整的字母组合，将其添加到结果列表res中。
	// 2. 横向遍历：遍历当前数字对应的所有字母，对于每个字母:

	// 3. 将字母添加到sb中（做选择）。
		public List<String> letterCombinations(String digits) {
			if (digits.length() == 0) return res;
			backtrack(digits, 0, new StringBuilder());
			return res;
		}

		// 回溯算法主函数
		private void backtrack(String digits, int start, StringBuilder sb) {
			// 如果sb的长度等于digits的长度，说明已经找到了一个完整的字母组合，将其添加到结果列表res中。
			if(sb.length() == digits.length()) {
				res.add(sb.toString());
				return;
			}
			// 回溯算法框架：横向遍历 + 纵向递归
//			for (int i = start; i < digits.length(); i++) {
//				String cur = mapping[digits.charAt(i) - '0'];
//				for (int j = 0; j < cur.length(); j++) {
//					sb.append(cur.charAt(j));
//					backtrack(digits, i + 1, sb);
//					sb.deleteCharAt(sb.length() - 1);
//				}
//			}
			/**
			 * 否则，遍历当前数字对应的所有字母，对于每个字母：
			 * 将字母添加到sb中（做选择）。
			 * 递归调用backtrack函数，处理下一个数字（递归下一层回溯树）。
			 * 从sb中移除最后一个字母（撤销选择）。
			 */
			for (int i = start; i < digits.length(); i++) {
				int digit = digits.charAt(i) - '0';
				for (char c : mapping[digit].toCharArray()) {
					// 做选择
					sb.append(c);
					// 递归下⼀层回溯树
					backtrack(digits, i + 1, sb);
					// 撤销选择
					sb.deleteCharAt(sb.length() - 1);
				}
			}
		}

	public static void main(String[] args) {

		LC_17_电话号码的字母组合2 lc = new LC_17_电话号码的字母组合2();
		LC_17_电话号码的字母组合2 lc1 = new LC_17_电话号码的字母组合2();
		LC_17_电话号码的字母组合2 lc2 = new LC_17_电话号码的字母组合2();
		System.out.println(lc.letterCombinations("23"));
		System.out.println(lc1.letterCombinations(""));
		System.out.println(lc2.letterCombinations("2"));
	}


}
